class Solution(object):
    def minimumMoves(self, grid):
        n = len(grid)
        dist = 0
        already = {(0,0,0,1)}
        st = {(0,0,0,1)}
        while st:
            next_st = set()
            for x0, y0, x1, y1 in st:
                if (x0, y0, x1, y1) == (n - 1, n - 2, n - 1, n - 1):
                    return dist
                if x0 == x1:
                    if y1 + 1 < n and not grid[x1][y1 + 1]:
                        next_node = (x1, y1, x1, y1 + 1)
                        if next_node not in already:
                            already.add(next_node)
                            next_st.add(next_node)
                    if x0 + 1 < n and not grid[x0 + 1][y0] and not grid[x0 + 1][y1]:
                        next_node = (x1, y0, x1 + 1, y0)
                        if next_node not in already:
                            already.add(next_node)
                            next_st.add(next_node)
                    if x0 + 1 < n and not grid[x0 + 1][y0] and not grid[x0 + 1][y1]:
                        next_node = (x0 + 1, y0, x0 + 1, y1)
                        if next_node not in already:
                            already.add(next_node)
                            next_st.add(next_node)                             
                else:
                    if x1 + 1 < n and not grid[x1 + 1][y0]:
                        next_node = (x1, y0, x1 + 1, y0)
                        if next_node not in already:
                            already.add(next_node)
                            next_st.add(next_node)
                    if y0 + 1 < n and not grid[x0][y0 + 1] and not grid[x1][y0 + 1]:
                        next_node = (x0, y0, x0, y0 + 1)                                        
                        if next_node not in already:
                            already.add(next_node)
                            next_st.add(next_node)
                    if y0 + 1 < n and not grid[x0][y0 + 1] and not grid[x1][y0 + 1]:
                        next_node = (x0, y0 + 1, x1, y0 + 1)
                        if next_node not in already:
                            already.add(next_node)
                            next_st.add(next_node)                        
            dist += 1
            st = next_st
        return -1
data = Solution()
grid = [[0,0,0,0,0,1],
               [1,1,0,0,1,0],
               [0,0,0,0,1,1],
               [0,0,1,0,1,0],
               [0,1,1,0,0,0],
               [0,1,1,0,0,0]]
print(data.minimumMoves(grid))